/**1. 两数之和
 * - 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
 */
export function twoSum(nums: number[], target: number): number[] {
    const map = new Map<number, number>()
    for (let i = 0; i < nums.length; i++) {
        if (map.has(target - nums[i])) {
            return [i, map.get(target - nums[i])!]
        }
        map.set(nums[i], i)
    }
    return []
}
/**242. 有效的字母异位词
 * - 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
 * - 注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
 */
export function isAnagram(s: string, t: string): boolean {
    if (s.length !== t.length) return false
    const map = new Map<string, number>()
    for (let i = 0; i < s.length; i++) {
        map.set(s[i], (map.get(s[i]) || 0) + 1) //正负相消为0，代表配对上了
        map.set(t[i], (map.get(t[i]) || 0) - 1)
    }
    console.log(map);
    for (const iterator of map) {
        if (iterator[1] !== 0) return false
    }
    return true
}
/**383. 赎金信
 * - 给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
 * - 如果可以，返回 true ；否则返回 false  
 */
export function canConstruct(ransomNote: string, magazine: string): boolean {


    //方法一：一次循环解决
    if (magazine.length < ransomNote.length) return false //杂志字母更少肯定不行
    const hash = new Array<number>(26).fill(0)
    const getIndex = (c: string) => c.charCodeAt(0) - 'a'.charCodeAt(0)
    //正负相消
    for (let i = 0; i < magazine.length; i++) {
        if (ransomNote[i]) hash[getIndex(ransomNote[i])]++
        hash[getIndex(magazine[i])]--
    }
    console.log(hash, hash.some((k) => k > 0));

    return !hash.some((k) => k > 0) //只要都小于等于0就行

    //其它方法

    // let aCode = 'a'.charCodeAt(0)
    // let arr: number[] = new Array(26).fill(0)

    // //判断杂志里的所有字符
    // for(let i = 0; i < magazine.length; i++){
    //     arr[magazine[i].charCodeAt(0) - aCode]++
    // }
    // //方法二，遍历一次赎金信+遍历一次arr
    // // //判断赎金信里面的所有字符
    // // for(let i = 0; i < ransomNote.length; i++){
    // //     arr[ransomNote[i].charCodeAt(0) - aCode]--
    // // }
    // // //如果两者正负相消之后，剩下的字符个数 >= 0，说明符合题目条件
    // // return arr.every(i => i >= 0)
    // //方法三，只需要遍历赎金信，判断里是否出现了<0的情况即可
    // for(let i = 0; i < ransomNote.length; i++){
    //     let index: number = ransomNote[i].charCodeAt(0) - aCode
    //     arr[index]--
    //     if(arr[index] < 0){
    //         return false
    //     }
    // }
    // return true
}
/**454. 四数相加 II
 * - 给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
 * - nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
 */
export function fourSumCount(nums1: number[], nums2: number[], nums3: number[], nums4: number[]): number {
    //思路：遍历1和2，把所有的两数之和和出现的次数记录下来
    // 然后遍历3和4，计算两数之和，看看在map是否出现过 0 - sum ，有的话结果就加上map中出现的次数 
    // 记录次数是因为，四元组可以重复，同样的结果可能有多种方式
    const map = new Map<number, number>()
    for (const n1 of nums1) {
        for (const n2 of nums2) {
            const sum = n1 + n2
            map.set(sum, (map.get(sum) || 0) + 1)
        }
    }
    let res = 0
    for (const n3 of nums3) {
        for (const n4 of nums4) {
            const sum = n3 + n4
            if (map.has(-sum)) {
                res += map.get(-sum)!
            }
        }
    }
    return res
}